#pragma once
#include "BinTreeNode.h"
#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;

class BinTree
{
private:
	BinTreeNode* ConstructTree(int* preBegin,int* preEnd);
	bool PreOrderVerify(BinTreeNode* bigTree,BinTreeNode* smallTree);
	bool DoesHaveChild(BinTreeNode* bigTree,BinTreeNode* smallTree);
	void PreOrderRecursion(BinTreeNode* root);
	void InOrderRecursion(BinTreeNode* root);
	void PostOrderRecursion(BinTreeNode* root);
	void PreOrderStack(BinTreeNode* root);
	void InOrderStack(BinTreeNode* root);
	void PostOrderStack(BinTreeNode* root);
	int TreeHeightRecursion(BinTreeNode* root);
	bool IsBalancedTree(BinTreeNode* root);
	void MirrorTreeRecursion(BinTreeNode* root);
	BinTreeNode* PreInBuildRecursion(int* preOrder,int* inOrder,int preBegin,int preEnd,int inBegin,int inEnd);

	BinTreeNode* OrderTreePostRecursion(int* orderPostTree,int beginIndex,int endIndex);
	void PrintTreeSumPath(BinTreeNode* root,vector<BinTreeNode*> nodeVector,int sum,int currentSum);
	void PrintVector(vector<BinTreeNode*> vec);

	void SearchToListRecursion(BinTreeNode* root,BinTreeNode** lastVisit);
	void SearchToListRecursion2(BinTreeNode* root,BinTreeNode* head,BinTreeNode* tail);
	void PrintTreeList(BinTreeNode* root);
	BinTreeNode* CommonNodeRecursion(BinTreeNode* root,int first,int second);
public:
	BinTree(void);
	~BinTree(void);

	void PreInOrderBuild(int preOrder[],int inOrder[],int preLength,int inLength);
	void VerifyChild(BinTreeNode* bigTree,BinTreeNode* smallTree);
	void IteratorTree(BinTreeNode* root);
	void TreeHeight(BinTreeNode* root);
	void MirrorBinTree(BinTreeNode* root);

	void OrderTreePostConstruct(int* orderPostTree,int length);
	void PrintTreePath(BinTreeNode* root,int sum);
	
	void SearchToDoubleList(BinTreeNode* root);

	void CommonNode(BinTreeNode* root,int first,int second);
	void CommonSearchNode(BinTreeNode* root,int first,int second);
	void BreadthSearch(BinTreeNode* root);
};

